package leetcode.L500;

import java.util.ArrayList;
import java.util.List;

public class Ex22 {
    List<String> list;
    public List<String> generateParenthesis(int n) {
        list = new ArrayList<>();
        dfs("",n,n);
        return list;
    }
    public void dfs(String str,int left,int right){
        if(left==0&&right==0){
            list.add(str);
            return;
        }
        if(left>right){
            return;
        }
        if(left>0){
            dfs(str+'(',left-1,right);
        }
        if(right>0){
            dfs(str+')',left,right-1);
        }
        return;
    }

    public static void main(String[] args) {
        Ex22 ex22 = new Ex22();
        ex22.generateParenthesis(3);
    }
}
